#include <bits/stdc++.h>

using namespace std;

//class Solution {
//public:
//    int subarraySum(vector<int> &nums, int k) {
//        int N = nums.size();
//        unordered_map<int, int> hash;
//        hash[nums[0]] = 1;
//        int total = 0;
//        for (int i = 1; i < N; ++i) {
//            int tmp = nums[i] += nums[i - 1];
//            total += hash[tmp - k];
//            ++hash[tmp];
//        }
//        total += hash[k];
//        return total;
//    }
//};

class Solution {
private:
    int subarraySum(vector<int> nums, int k) {
        int N = nums.size();
        unordered_map<int, int> hash;
        hash[nums[0]] = 1;
        int total = 0;
        for (int i = 1; i < N; ++i) {
            int tmp = (nums[i] += nums[i - 1]);
            total += hash[tmp - k];
            ++hash[tmp];
        }
        total += hash[k];
        return total;
    }

public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
        int ans = 0;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) { // 枚举上边界
            vector<int> sum(n);
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                ans += subarraySum(sum, target);
            }
        }
        return ans;
    }
};

int main() {
    vector<int> nums = {1, 1, 1};
    int k = 2;
    Solution solution;
    vector<vector<int>> matrix = {
            {1,  -1},
            {-1, 1},
//            {0, 1, 0},
    };
    solution.numSubmatrixSumTarget(matrix, 0);
//    solution.subarraySum(nums, k);
}